package com.lfg.other;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class NSum {


    public static void main(String[] args) {
        Integer[] ret = sum(new Integer[]{41, 1, 3, 5}, new Integer[]{72, 4, 6, 8});
        System.out.println("[" + JSON.toJSONString(ret) + "]");


        Integer[] ret2 = sum(new Integer[]{1, 2, 3}, new Integer[]{4, 5, 6});
        System.out.println("[" + JSON.toJSONString(ret2) + "]");
        // 6 15  9
    }

    public static Integer[] sum(Integer[] array1, Integer[] array2) {
        Arrays.sort(array1, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        Arrays.sort(array2, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });

        PriorityQueue<Integer> queue = new PriorityQueue<>(array1.length, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array2.length; j++) {
                int num = array1[i] + array2[j];
                if (queue.size() >= array1.length) {
                    Integer peek = queue.peek();
                    if (peek < num) {
                        break;
                    } else {
                        queue.poll();
                    }
                }
                queue.add(num);
            }
        }
        Integer[] ret = new Integer[array1.length];
        int idx = 0;
        while (!queue.isEmpty()) {
            ret[idx++] = queue.poll();
        }

        return ret;
    }
}
//
// 11 16  = 4